\documentclass{classrep}
\usepackage[utf8]{inputenc}
\usepackage{color}
\usepackage{graphicx}
\usepackage{placeins}

\studycycle{Informatyka, studia dzienne, II st.}
\coursesemester{III}

\coursename{Nowoczesne Techniki Programowania}
\courseyear{2013/2014}

\courseteacher{Dariusz Puchała, Kamil Stokfiszewski}
\coursegroup{czwartek, 14:15}

\author{
  \studentinfo{Rafał Mościński}{nr 186844} \and
  \studentinfo{Marcin Kubczak}{nr 186834} 
}

\title{Zadanie Numer 1: Analiza złożoności obliczeniowej i profilowanie algorytmów.}

\begin{document}
\maketitle

\section{Cel}
{ 
Celem ćwiczenia jest zdobycie umiejętności praktycznych z zakresu analitycznej i eksperymentalnej oceny złożoności obliczeniowej algorytmów. W ramach zadania przeanalizowany zostanie algorytm quicksort. Analiza obejmować będzie następujące kroki: 
\begin{itemize}
\item Przeanalizowanie pesymistycznej, optymistycznej oraz średniej złożoności obliczeniowej algorytmu.
\item oszacowanie czasu procesora potrzebnego na wykonanie algorytmu
\item matematyczna analiza algorytmu obejmująca także sporządzenie wykresu zależności czasu od ilości elementów w tablicy do posortowania.
\end{itemize}
 }

\section{Wprowadzenie}
{
\subsection{Złożoność obliczeniowa}
"Analiza złożoności obliczeniowej może dotyczyć takich operacji, jak operacje:
\begin{itemize}
\item arytmetyczne: dodawanie (odejmowanie), mnożenie, dzielenie;
\item logiczne: porównania, bitowa alternatywa, koniunkcja i tym podobne.
\item przesyłania danych pomiędzy komórkami pamieci.
\end{itemize}
Analiza złożoności polega na wyznaczeniu funkcji argumentu n, gdzie n to rozmiar zadania, która stanowi oszacowanie ilości operacji arytmetycznych lub liczby komórek pamięci, przy czym najczęsciej brany pod uwagę jest rząd wielkości.

Złożoność pesymistyczna to najmniej korzystna, tj. najwieksza, złożoność ze wszystkich możliwych do uzyskania operujac na zbiorach danych o długości n.

Złożoność średnia (oczekiwana) bierze pod uwagę prawdopodobieństwo wystapienia każdego zestawu danych."[1]

\subsection{Algorytm quicksort}
W algorytmie quicksort wybierany jest element znajdujący się na środku tablicy, po czym poruszamy się z krawędzi tablicy (najwyższego oraz najniższego indeksu) do środka, sprawdzając, czy na każdym z indeksów znajduje się liczba odpowiednio mniejsza oraz większa niż element środkowy. W przeciwnym wypadku elementy są zamieniane ze sobą miejscami.


\section{Opis implementacji}
{
Aplikacja napisana została w języku Java. Do pomiaru czasu wykorzystano funkcję nanoTime() klasy System dostarczanej przez bibliotekę Java, która odczytuje wartość wewnętrznego licznika systemowego pomiaru czasu.
}

\section{Materiały i metody}
{
W przypadku algorytmu opracowywanego w ramach zadania laboratoryjnego pod uwagę brany został czas procesora potrzebny do posortowania tablicy metodą quicksort dla różnych ilości elementów w tablicy. Rozważono przypadek optymistyczny,pesymistyczny oraz średni. W celu zwiększenia wiarygodności obliczeń pomiary wykonywane zostały 50-krotnie dla każdego zestawu danych, ostateczny wynik jest medianą z 50 prób. Wykonano wykresy czasu procesora potrzebnego do wykonania algorytmu w zależności od ilości elementów.
}
\section{Wyniki}
{
Poniżej przedstawiono uzyskane pomiary czasowe dla różnej ilości elementów w tablicy:



Przypadek optymistyczny (elementy w tablicy poukładane są w dobrej kolejności):
\begin{table}[h!]
\centering
\caption{Przypadek optymistyczny}

\begin{tabular}{|c|c|}
\hline
Wielkość tablicy & mediana z 50 prób czasu   \\
10000 & 95312,68 \\
20000 & 289967,08  \\
30000 & 549061,22 \\
40000 & 696775,82  \\
50000 & 818034,68  \\
60000 & 921453,9  \\
70000 & 1038788,6\\
80000 & 1240973,86  \\
90000 & 1352705,02 \\
100000 & 1478708,26 \\
\hline
\end{tabular} 

\end{table}

Przypadek  średni (elementy w tablicy poukładane są w losowej kolejności):
\FloatBarrier
\begin{table}[h!]
\centering
\caption{Przypadek średni}

\begin{tabular}{|c|c|}
\hline
Wielkość tablicy & mediana z 50 prób czasu   \\
10000 & 180488,02 \\
20000 & 198281,64  \\
30000 & 422674,72  \\
40000 & 417322,44  \\
50000 & 728674,88  \\
60000 & 864920,38 \\
70000 & 923383,16  \\
80000 & 1011718,26 \\
90000 & 1157861,5 \\
100000 & 1514452,2  \\
\hline
\end{tabular} 


\end{table}

Przypadek pesymistyczny (elementy w tablicy poukładane są w odwrotnej kolejności):

\begin{table}[h!]
\centering
\caption{Przypadek pesymistyczny}

\begin{tabular}{|c|c|}
\hline
Wielkość tablicy & mediana z 50 prób czasu   \\
10000 & 273707,1 \\
20000 & 319190,7 \\
30000 & 330443,36\\
40000 & 432977,36 \\
50000 & 567028,16  \\
60000 & 757137,58  \\
70000 & 991335,7  \\
80000 & 1065063,68  \\
90000 & 1206671,82  \\
100000 & 1614375,24  \\
\hline
\end{tabular} 


\end{table}








Poniżej przedstawiono wykresy zależności czasu procesora potrzebnego na wykonanie algorytmu od ilości elementów w tablicy:
\FloatBarrier
\begin{figure}[ht!]
\centering
\includegraphics[width=90mm]{optymistyczny.png}
\caption{Przypadek optymistyczny}
\label{overflow}
\end{figure}
\FloatBarrier
\begin{figure}[ht!]
\centering
\includegraphics[width=90mm]{sredni.png}
\caption{Przypadek średni}
\label{overflow}
\end{figure}
\FloatBarrier
\begin{figure}[ht!]
\centering
\includegraphics[width=90mm]{pesymistyczny.png}
\caption{Przypadek pesymistyczny}
\label{overflow}
\end{figure}

}

\section{Dyskusja i wnioski}
{
Na podstawie uzyskanych pomiarów obliczono, że złożoność algorytmu quicksort w zależności od ilości elementów jest następującego rzędu:
\begin{itemize}
\item Dla przypadku optymistycznego:
\begin{equation}
Time(n)=O(nlog_2n)
\end{equation} 
\item Dla przypadku pesymistycznego:
\begin{equation}
Time(n)=O(n^2)
\end{equation}
\end{itemize}
}

Na podstawie danych dobranych odpowiednio dla przypadku pesymistycznego, optymalnego oraz średniego (pseudolosowo), można oszacować, że czas wykonania sortowania znajduje się w rzeczywistości pomiędzy czasami wyznaczonymi na zbiorach z danymi optymalnymi i nieoptymalnymi.

\begin{thebibliography}{0}
\item Materiały wykładowe. Wykład 1 - Analiza złożoności obliczeniowej i pamięciowej.
\end{thebibliography}
\end{document}
